package DP.背包.万诺复习;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
无限零钱322 - void100就超时 - 改为 int amount-
 */
public class 无限零钱_版本2_int_amount减 {
    // int_amount减  (无map
    private int b(int faAm) {
        if(faAm == 0){
            return 0;
        }

        int m = 99999;
        for (int i = 0; i < p.length; i++) {
            if(faAm - p[i] < 0){
                continue;
            }
            m = Math.min(
                    1 + b(faAm-p[i])
                    ,m
            );
        }
        return m;
    }

    @Test
    public void test() {
        int[] c = {1,2,5};
        int a = 11;
        System.out.println(coinChange(c,a));
    }

    int[] p;
    int am;
    public int coinChange(int[] coins, int amount) {
        p = coins;
        am = amount;
        int faAm = amount;
        int minGe = b(faAm); // faSum=要算 算 (要算)
//        return minGe;
        return minGe==99999?-1:minGe; // 少：可能没找到
    }

    // 加map
    Map<String, Integer> map = new HashMap<>();
    private int b2(int faAm) {
        if(faAm == 0){
            return 0;
        }


        String key = faAm+"";
        if(map.containsKey(key)){
            return map.get(key);
        }

        int m = 99999;
        for (int i = 0; i < p.length; i++) {
            if(faAm - p[i] < 0){
                continue;
            }
            m = Math.min(
                    1 + b2(faAm-p[i])
                    ,m
            );
        }

        map.put(key, m);
        return m;
    }
}
